package com.wengu.algorithm.alg;


import com.wengu.algorithm.dto.TaskAlg;
import com.wengu.algorithm.dto.UserAlg;
import com.wengu.algorithm.entity.AssignmentOutcome;
import com.wengu.algorithm.service.AssignmentOutcomeUserService;
import lombok.extern.slf4j.Slf4j;

import java.util.*;
import java.util.stream.Collectors;

@Slf4j
public class QAOTO {

    private static final int MAX_SEARCH_DEPTH = 50;
    private static final int MAX_NODES = 500;


    public List<TaskAlg> allocateTasksQAOTO(UserAlg user, List<TaskAlg> allTasks,
                                            AssignmentOutcome assignmentOutcome,
                                            AssignmentOutcomeUserService assignmentOutcomeUserService,
                                            Map<Long, TaskAlg> taskCacheMap, Map<Long, TaskAlg> realTaskCacheMap,String algName,
                                            Set<Long> notIncreaseTaskIdSet) {

        List<TaskAlg> selected = qaotoBranchAndBound(user, allTasks, taskCacheMap, notIncreaseTaskIdSet);
        // 过滤出真正执行的任务，考虑执行成本
        // 按照顺序遍历该用户选中的路径中的任务，重新计算费用，考虑任务的执行成本。将超出预算的任务剔除
        double usedCost = 0;
        double distanceTotalCost = 0;
        double executionTotalCost = 0;
        // 真正被选中的任务集合，剔除超出预算的任务
        List<TaskAlg> realSelected = new ArrayList<>();
        int lastX = user.startX;
        int lastY = user.startY;
        // 计算真实的任务的质量
        for (int i = 0; i < selected.size(); i++) {
            realSelected = selected;
            TaskAlg taskAlg = selected.get(i);
            double distanceCost = calculateDistance(lastX, lastY, taskAlg.taskX, taskAlg.taskY);
            usedCost += distanceCost + taskAlg.executionCost;
            // 如果总成本超出预算，则剔除后面的任务
            double finalTrip = calculateFinalTrip(taskAlg, user);
            if (usedCost + finalTrip > user.budget) {
                realSelected = selected.subList(0, i);
                break;
            }
            lastX = taskAlg.taskX;
            lastY = taskAlg.taskY;
        }

        lastX = user.startX;
        lastY = user.startY;
        // 将真实的任务进行处理，只保存真正执行完的任务，用于计算真实的质量增量
        for (int i = 0; i < realSelected.size(); i++) {
            TaskAlg taskAlg = realSelected.get(i);
            TaskAlg realTask = realTaskCacheMap.get(taskAlg.getId());
            if (realTask == null) {
                realTask = new TaskAlg();
                realTaskCacheMap.put(taskAlg.id, realTask);
                realTask.k = 1;
                realTask.successProb = taskAlg.successProb;
            } else {
                realTask.k++;
            }
            double distanceCost = calculateDistance(lastX, lastY, taskAlg.taskX, taskAlg.taskY);
            distanceTotalCost += distanceCost;
            executionTotalCost += taskAlg.executionCost;
            lastX = taskAlg.taskX;
            lastY = taskAlg.taskY;
        }
        if (realSelected.isEmpty()) {
            user.distanceCost = calculateDistance(user.startX, user.startY, user.destX, user.destY);
            user.executionCost = 0;
        } else {
            double finalTrip = calculateFinalTrip(realSelected.get(realSelected.size()-1), user);
            user.distanceCost = distanceTotalCost + finalTrip;
            user.executionCost = executionTotalCost;
        }
        user.usedCost = user.distanceCost + user.executionCost;
        // 计算用户总效用值
        double userTotalDeltaF = calculateTotalDeltaF(realSelected);
        // 保存用户执行结果详情表
        assignmentOutcomeUserService.saveOutcomeUser(user, assignmentOutcome, realSelected, userTotalDeltaF);
        log.info("用户[{}]执行平台安排的任务后的质量增量总和为[{}]", user.id, userTotalDeltaF);
        return realSelected;
    }

    /**
     * QAOTO算法核心：基于分支定界的深度优先搜索
     */
    public List<TaskAlg> qaotoBranchAndBound(UserAlg user, List<TaskAlg> allTasks,
                                             Map<Long, TaskAlg> taskCacheMap,
                                             Set<Long> notIncreaseTaskIdSet) {

        // 过滤有效任务
        List<TaskAlg> feasibleTasks = filterFeasibleTasks(user, allTasks, taskCacheMap, notIncreaseTaskIdSet);
        if (feasibleTasks.isEmpty()) {
            return new ArrayList<>();
        }

        // 初始化最佳解
        List<TaskAlg> bestSolution = new ArrayList<>();
        double bestQuality = 0.0;

        // 开始分支定界搜索
        Stack<SearchNode> stack = new Stack<>();

        // 根节点：空路径
        SearchNode root = new SearchNode(new ArrayList<>(), 0.0, 0.0, user.startX, user.startY);
        stack.push(root);
        int nodeCount = 0;
        while (!stack.isEmpty()  && nodeCount < MAX_NODES) {
            nodeCount++;
            SearchNode currentNode = stack.pop();

            // 计算当前节点的上界，用于剪枝
            double upperBound = calculateUpperBound(currentNode, feasibleTasks, user, taskCacheMap);

            // 剪枝：如果上界小于当前最优解，则跳过该分支
            if (upperBound <= bestQuality && bestQuality > 0) {
                continue;
            }

            // 检查当前节点是否比当前最优解更好
            if (currentNode.totalQuality > bestQuality) {
                bestQuality = currentNode.totalQuality;
                bestSolution = new ArrayList<>(currentNode.path);
            }

            // 扩展子节点（分支）
            for (TaskAlg task : feasibleTasks) {
                if (!currentNode.containsTask(task.id)) {
                    SearchNode childNode = createChildNode(currentNode, task, user, taskCacheMap);

                    // 检查子节点是否可行（预算约束）
                    if (childNode != null && isFeasible(childNode, user)) {
                        stack.push(childNode);
                    }
                }
            }
        }

        // 更新任务缓存和执行次数
        updateTaskCacheAndUserCost(bestSolution, user, taskCacheMap);

        return bestSolution;
    }

    /**
     * 搜索节点类（用于分支定界）
     */
    private static class SearchNode {
        List<TaskAlg> path;           // 当前路径中的任务
        double totalCost;              // 当前总成本
        double totalQuality;           // 当前总质量
        double lastX, lastY;           // 最后一个任务的位置
        Set<Long> assignedTaskIds;      // 已分配任务ID集合

        public SearchNode(List<TaskAlg> path, double totalCost, double totalQuality,
                          double lastX, double lastY) {
            this.path = new ArrayList<>(path);
            this.totalCost = totalCost;
            this.totalQuality = totalQuality;
            this.lastX = lastX;
            this.lastY = lastY;
            this.assignedTaskIds = path.stream()
                    .map(task -> task.id)
                    .collect(Collectors.toSet());
        }

        public boolean containsTask(Long taskId) {
            return assignedTaskIds.contains(taskId);
        }
    }

    /**
     * 创建子节点（分支操作）
     */
    private SearchNode createChildNode(SearchNode parent, TaskAlg task, UserAlg user,
                                       Map<Long, TaskAlg> taskCacheMap) {
        // 计算移动到新任务的成本
        double distanceCost = calculateDistance(parent.lastX, parent.lastY, task.taskX, task.taskY);
        double additionalCost = distanceCost;

        // 检查是否超预算（包含返回行程）
        double finalTripCost = calculateDistance(task.taskX, task.taskY, user.destX, user.destY);
        if (parent.totalCost + additionalCost + finalTripCost > user.budget) {
            return null;
        }

        // 计算质量增量
        TaskAlg cachedTask = taskCacheMap.putIfAbsent(task.id, task);
        double deltaF = calculateTaskDeltaF(task, cachedTask);

        if (deltaF <= 0) {
            return null;
        }

        // 创建新路径
        List<TaskAlg> newPath = new ArrayList<>(parent.path);
        TaskAlg taskCopy = copyTask(task);
        taskCopy.deltaF = deltaF;
        newPath.add(taskCopy);

        // 计算新节点的总成本和质量
        double newTotalCost = parent.totalCost + additionalCost;
        double newTotalQuality = parent.totalQuality + deltaF;

        return new SearchNode(newPath, newTotalCost, newTotalQuality, task.taskX, task.taskY);
    }

    /**
     * 计算节点的上界（用于定界剪枝）
     */
    private double calculateUpperBound(SearchNode node, List<TaskAlg> feasibleTasks,
                                       UserAlg user, Map<Long, TaskAlg> taskCacheMap) {
        double remainingBudget = user.budget - node.totalCost;
        if (remainingBudget <= 0) {
            return node.totalQuality;
        }

        // 计算剩余任务的质量密度上界（松弛上界）
        double upperBound = node.totalQuality;

        // 获取未分配的任务
        List<TaskAlg> unassignedTasks = feasibleTasks.stream()
                .filter(task -> !node.containsTask(task.id))
                .collect(Collectors.toList());

        // 按质量密度排序（贪心上界）
        List<TaskAlg> sortedTasks = unassignedTasks.stream()
                .sorted((t1, t2) -> {
                    double density1 = calculateQualityDensity(t1, node.lastX, node.lastY, taskCacheMap);
                    double density2 = calculateQualityDensity(t2, node.lastX, node.lastY, taskCacheMap);
                    return Double.compare(density2, density1);
                })
                .collect(Collectors.toList());

        // 贪心添加任务直到预算用完
        double currentX = node.lastX;
        double currentY = node.lastY;
        double currentCost = 0;

        for (TaskAlg task : sortedTasks) {
            double moveCost = calculateDistance(currentX, currentY, task.taskX, task.taskY);
            double taskCost = moveCost;
            double finalTripCost = calculateDistance(task.taskX, task.taskY, user.destX, user.destY);

            if (currentCost + taskCost + finalTripCost <= remainingBudget) {
                double deltaF = calculateTaskDeltaF(task, taskCacheMap.get(task.id));
                upperBound += deltaF;
                currentCost += taskCost;
                currentX = task.taskX;
                currentY = task.taskY;
            }
        }

        return upperBound;
    }

    /**
     * 计算任务质量密度（用于排序）
     */
    private double calculateQualityDensity(TaskAlg task, double fromX, double fromY,
                                           Map<Long, TaskAlg> taskCacheMap) {
        double distance = calculateDistance(fromX, fromY, task.taskX, task.taskY);
//        double totalCost = distance + task.executionCost;
        double deltaF = calculateTaskDeltaF(task, taskCacheMap.get(task.id));

        return deltaF / distance;
    }

    /**
     * 计算任务质量增量
     */
    private double calculateTaskDeltaF(TaskAlg task, TaskAlg cachedTask) {
        if (cachedTask != null && cachedTask.totalF >= 1.0) {
            return 0;
        }
        if (cachedTask != null) {
            task.k=cachedTask.k;
        }
        return task.calDeltaFCommon();
    }

    /**
     * 检查节点是否可行
     */
    private boolean isFeasible(SearchNode node, UserAlg user) {
        double finalTripCost = calculateDistance(node.lastX, node.lastY, user.destX, user.destY);
        return node.totalCost + finalTripCost <= user.budget;
    }

    /**
     * 过滤可行任务
     */
    private List<TaskAlg> filterFeasibleTasks(UserAlg user, List<TaskAlg> allTasks,
                                              Map<Long, TaskAlg> taskCacheMap,
                                              Set<Long> notIncreaseTaskIdSet) {
        return allTasks.stream()
                .filter(task -> {
                    TaskAlg cached = taskCacheMap.get(task.id);
                    // 过滤总质量已超过1的任务
                    if (cached != null && cached.totalF >= 1.0) {
                        notIncreaseTaskIdSet.add(task.id);
                        return false;
                    }

                    return true;
                })
                .collect(Collectors.toList());
    }

    /**
     * 复制任务对象
     */
    private TaskAlg copyTask(TaskAlg original) {
        TaskAlg copy = new TaskAlg();
        copy.id = original.id;
        copy.taskX = original.taskX;
        copy.taskY = original.taskY;
        copy.executionCost = original.executionCost;
        copy.successProb = original.successProb;
        copy.k = original.k;
        copy.totalF = original.totalF;
        return copy;
    }

    /**
     * 更新任务缓存和用户成本
     */
    private void updateTaskCacheAndUserCost(List<TaskAlg> solution, UserAlg user,
                                            Map<Long, TaskAlg> taskCacheMap) {
        if (solution.isEmpty()) return;

        // 计算实际路径成本
        double totalCost = 0;
        double lastX = user.startX;
        double lastY = user.startY;

        for (TaskAlg task : solution) {
            double distanceCost = calculateDistance(lastX, lastY, task.taskX, task.taskY);
            totalCost += distanceCost;
            lastX = task.taskX;
            lastY = task.taskY;

            // 更新任务缓存
            TaskAlg cached = taskCacheMap.get(task.id);
            if (cached == null) {
                cached = new TaskAlg();
                cached.id = task.id;
                cached.k = 0;
                cached.totalF = 0;
                taskCacheMap.put(task.id, cached);
            }
            cached.k++;
            cached.totalF += task.deltaF;
            task.k++;
        }

        // 添加返回行程成本
        double finalTrip = calculateDistance(lastX, lastY, user.destX, user.destY);
        totalCost += finalTrip;

        user.usedCost = totalCost;
        user.distanceCost = totalCost ;
    }

    // 保留原有的工具方法
    public double calculateTotalDeltaF(List<TaskAlg> path) {
        return path.stream().mapToDouble(TaskAlg::calDeltaFCommon).sum();
    }

    public double calculateDistance(double x1, double y1, double x2, double y2) {
        return Math.sqrt(Math.pow(x1-x2, 2) + Math.pow(y1-y2, 2));
    }

    public double calculateFinalTrip(TaskAlg lastTask, UserAlg user) {
        return calculateDistance(lastTask.taskX, lastTask.taskY, user.destX, user.destY);
    }

}
